home *** CD-ROM | disk | FTP | other *** search
/ Aminet 21 / Aminet 21 (1997)(GTI - Schatztruhe)[!][Oct 1997].iso / Aminet / dev / c / BinaryTrees.lzh / BinaryTrees.readme next >
Encoding:
Text File  |  1997-08-06  |  1.0 KB  |  25 lines
  1. Short: Binary AVL & Splay trees non-recursive.
  2. Uploader: crh@ubiqx.mn.org (Christopher R. Hertel)
  3. Author: crh@ubiqx.mn.org (Christopher R. Hertel)
  4. Type: dev/c
  5. Version: 2.4.
  6.  
  7. Written in C using OOP techniques, these modules provide three forms of
  8. binary tree: Simple (unbalanced) AVL (height-balanced), and Splay.  AVL
  9. trees are re-balanced after every insertion or deletion.  For each node in
  10. the tree, the difference in height between the left and right subtree is
  11. at most 1.  Splay trees use a different approach.  Each time a node is
  12. accessed (inserted, deleted, or directly found via a search), the node is
  13. bubbled to the top of the tree.  This has the effect of making the tree
  14. 'bushier' and placing the most frequently accessed nodes nearer to the
  15. top.
  16.  
  17. The functions are non-recursive to limit stack space usage, and can also
  18. be made into a run-time library.  The type of tree used is determined by
  19. which header file is included with your program.  No other code changes
  20. are necessary.
  21.  
  22. Pretty darn fast, too, IMHO. 
  23.  
  24. Chris Hertel
  25.